class Solution {
public:
    int next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
    bool ret = false;
    bool vist[7][7];
    int m;
    int n;

    bool dfs(vector<vector<char>>& board, string& word, int x, int y, int cur)
    {
        if (cur == word.size() - 1) return true;

        for (auto e : next)
        {
            int nx = e[0] + x, ny = e[1] + y;
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || vist[nx][ny] == true || board[nx][ny] != word[cur + 1]) continue;

            vist[nx][ny] = true;
            if (dfs(board, word, nx, ny, cur + 1) == true) return true;
            vist[nx][ny] = false;
        }

        return false;
    }
    bool exist(vector<vector<char>>& board, string& word)
    {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                vist[i][j] = false;
            }

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
            {
                if (word[0] != board[i][j]) continue;
                vist[i][j] = true;
                if (dfs(board, word, i, j, 0) == true) return true;
                vist[i][j] = false;
            }

        return false;
    }
};